package com.sheng.leetcode.year2023.month08.day30;

import lombok.var;
import org.junit.Test;

import java.util.*;

/**
 * @author by ls
 * @date 2023/8/30
 * <p>
 * 1654. 到家的最少跳跃次数<p>
 * <p>
 * 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。<p>
 * 跳蚤跳跃的规则如下：<p>
 * 它可以 往前 跳恰好 a 个位置（即往右跳）。<p>
 * 它可以 往后 跳恰好 b 个位置（即往左跳）。<p>
 * 它不能 连续 往后跳 2 次。<p>
 * 它不能跳到任何 forbidden 数组中的位置。<p>
 * 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。<p>
 * 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，<p>
 * 同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9<p>
 * 输出：3<p>
 * 解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。<p>
 * <p>
 * 示例 2：<p>
 * 输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11<p>
 * 输出：-1<p>
 * <p>
 * 示例 3：<p>
 * 输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7<p>
 * 输出：2<p>
 * 解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。<p>
 * <p>
 * 提示：<p>
 * 1 <= forbidden.length <= 1000<p>
 * 1 <= a, b, forbidden[i] <= 2000<p>
 * 0 <= x <= 2000<p>
 * forbidden 中所有位置互不相同。<p>
 * 位置 x 不在 forbidden 中。<p>
 */
public class LeetCode1654 {

    @Test
    public void test01() {
        int[] forbidden = {14, 4, 18, 1, 15};
        int a = 3, b = 15, x = 9;
//        int[] forbidden = {8, 3, 16, 6, 12, 20};
//        int a = 15, b = 13, x = 11;
//        int[] forbidden = {1, 6, 2, 14, 5, 17, 4};
//        int a = 16, b = 9, x = 7;
        System.out.println(new Solution().minimumJumps(forbidden, a, b, x));
    }
}

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> s = new HashSet<>();
        // 将不允许踩的点位放入集合 s 中
        for (int v : forbidden) {
            s.add(v);
        }
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 1});
        final int n = 6000;
        boolean[][] vis = new boolean[n][2];
        vis[0][1] = true;
        for (int ans = 0; !q.isEmpty(); ++ans) {
            for (int t = q.size(); t > 0; --t) {
                var p = q.poll();
                int i = p[0], k = p[1];
                if (i == x) {
                    return ans;
                }
                List<int[]> nxt = new ArrayList<>();
                nxt.add(new int[]{i + a, 1});
                if ((k & 1) == 1) {
                    nxt.add(new int[]{i - b, 0});
                }
                for (var e : nxt) {
                    int j = e[0];
                    k = e[1];
                    if (j >= 0 && j < n && !s.contains(j) && !vis[j][k]) {
                        q.offer(new int[]{j, k});
                        vis[j][k] = true;
                    }
                }
            }
        }
        return -1;
    }
}
